/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/9/5 上午 11:13
 */
public class day190905 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }

//    public int maxDepth(TreeNode root) {
//        int deep = 0;
//        if (root == null) {
//            return 0;
//        }
//        return Math.max(getDeep(root.left, deep + 1), getDeep(root.right, deep + 1));
//    }
//
//    public int getDeep(TreeNode root, int deep) {
//        if (root == null) {
//            return deep;
//        }
//        return Math.max(getDeep(root.left, deep + 1), getDeep(root.right, deep + 1));
//    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    }

    public boolean isValidBST(TreeNode root) {
        return help(root, null, null);
    }

    private boolean help(TreeNode root, Integer lower, Integer upper) {
        if (root == null) {
            return true;
        }
        if (lower != null && root.val <= lower) {
            return false;
        }
        if (upper != null && root.val >= upper) {
            return false;
        }
        if (!help(root.left, lower, root.val)) {
            return false;
        }
        if (!help(root.right, root.val, upper)) {
            return false;
        }
        return true;
    }

//    public boolean isValidBST(TreeNode root) {
//        Stack<TreeNode> nodeStack = new Stack<>();
//        double value = - Double.MAX_VALUE;
//
//        while (!nodeStack.isEmpty() || root != null) {
//            while (root != null) {
//                nodeStack.add(root);
//                root = root.left;
//            }
//            root = nodeStack.pop();
//            if (root.val <= value) {
//                return false;
//            }
//            value = root.val;
//            root = root.right;
//        }
//        return true;
//    }

//    public boolean hasPathSum(TreeNode root, int sum) {
//        if (root == null) {
//            return false;
//        }
//        if (root.val - sum == 0 && root.left == null && root.right == null) {
//            return true;
//        }
//        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
//    }

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        sum -= root.val;
        if (root.left == null && root.right == null) {
            return sum == 0;
        }
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }

    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 10;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 10;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - 2]) * (10 - i - 1);
        }
        return dp[n];
    }

}
